package BsearchTree;

import sun.reflect.generics.tree.Tree;
import sun.util.resources.cldr.az.CalendarData_az_Cyrl_AZ;

public class BinarySearchTree {

    //创建二叉树的节点
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root;

    //查找方法
    public boolean search(int val){
        TreeNode cur = root;
        while(cur != null){
            if(cur.val < val){
                cur = cur.right;
            }else if(cur.val > val){
                cur = cur.left;
            }else{
                return true;
            }
        }
        return false ;
    }

    //插入方法
    public void insert(int val){
        //如果根节点为空,则将值直接插入到创建的根节点里面
        if(root == null){
            root = new TreeNode(val);
            return;
        }
        //记录要插入的节点
        TreeNode inser  = new TreeNode(val);
        //新创一个节点,从根节点开始用于遍历树的每一个节点与插入值比较,去查找插入的位置
        TreeNode cur = root;
        //用一个节点记录下cur遍历的节点,再让cur指向下一个节点
        //因为当我们的cur走到null时,此时插入节点就应该是它的父母节点的下一个位置
        TreeNode parent = null;
        //现在根基节点不为空.讨论cur这个遍历节点和所有节点之间查找插入位置的路线
        while(cur != null){
            if(cur.val > val){
                parent = cur;
                cur = cur.left;
            }else if(cur.val < val){
                parent = cur ;
                cur = cur.right;
            }else{
                return;
            }
        }

        //现在根节点不为空,但是cur为空,说明parent指向叶子结点了,此时就可以插入元素了
        if(parent.val > inser.val){
            parent.left = inser;
        }else{
            parent.right = inser;
        }
    }

    //先找到要删除的节点 - > 找到要删除节点的方法
    public  void remove(int val){
        //当要删除的节点就是根节点的时候
        TreeNode cur = root;
        //直接让父亲节点置为空
        TreeNode parent = null;
        //当删除的节点不是根结点时
        while(cur != null){
            if (cur.val > val){
                parent = cur;
                cur = cur.left;
            }else if(cur.val < val){
                parent = cur;
                cur = cur.right;
            }else{//找到要删除的节点,调用removeNode方法进行删除
                removeNode(parent , cur);
                return;
            }
        }

    }

    //删除节点的方法
    public void removeNode(TreeNode parent , TreeNode cur){
        if(cur.left == null){ //左子树为空的前提下
            if(cur == root) {
                root = cur.right;
            }else if(cur == parent.right){
                parent.right = cur.right;
            }else{
                parent.left = cur.right;
            }

        }else if(cur.right == null){ //右子树为空的前提下
            if (cur == root){
                root = cur.left;
            }else if(cur == parent.left){
                parent.left = cur.left;
            }else{
                parent.right = cur.right;
            }

        }else{
            //左右子树都不为空的情况
            //有两种替代删除的方式,可以用左子树最大值替代要删除的节点或右子树最小值替代要删除节点
            //这里以右子树最小值->找最小右子树 来替代要删除节点为例

            //定义两个节点tp , t分别记录cur这个要删除的节点的替换节点的父母节点 和 替换节点
            TreeNode tp = cur;
            TreeNode t = cur.right;

            //当右孩子有左树时
            while(t.left != null){
                tp = t; //记录下孩子节点
                t = t.left; //
            }
            cur.val = t.val;//将找到的要删除的节点的右子树的最小值节点t的值替换删除节点的值.

            //判断删除节点的右子树是否有左孩子
            if(tp.left == t){
                //如果有左孩子,则这个左孩子就是替换删除节点的那个节点,上面替换完值以后
                //我们这里要将这个替换的孩子节点删除掉
                tp.left = t.right;
            }else{
                tp.right = t.right;
            }
        }
    }

}
